#include "LinkStack.h"


int Partition(int *a,int start, int end)
{
    int left = start;
    int right = end;
    int temp = a[left]; // 将最左边的值定为基准值
    while (left < right)
    {
        // 右边往左动，找比基准值小的数
        while (a[right] > temp && left < right)
            right--;
        if (left < right)
            a[left++] = a[right]; // 把右边比基准值小的数扔到左边

        // 左边往右动，找比基准值大的数
        while (a[left] < temp && left < right)
            left++;
        if (left < right)
            a[right--] = a[left]; // 把左边比基准值大的数扔到右边
    }
    a[left] = temp;
    return left;
}


//快速排序的非递归实现
void Fast_No_Recur(int *a,int start,int end)
{
    LinkStack s;
    // 把区间的下标入栈
    s.Push((void*)(long)start);
    s.Push((void*)(long)end);
    while(!s.IsEmpty()) //栈不为空：栈内仍存在未排序的区间
    {
        //拿出区间
        long right = (long)*s.GetTop();
        s.Pop();
        long left = (long)*s.GetTop();
        s.Pop();

        //分组排序
        long mid = Partition(a,left,right);
        if(left < mid-1) //左区间存在
        {
            //左区间入栈
            s.Push((void*)(long)left);
            s.Push((void*)(long)(mid-1));
        }
        if(mid+1<right) //右区间
        {
            //右区间入栈
            s.Push((void*)(long)(mid+1));
            s.Push((void*)(long)right);
        }
    }
}





int main(int argc, char* argv[])
{

    // LinkStack a;
    // for(long i = 0;i<10;i++)
    // {
    //     a.Push((void*)(i+1));
    // }
    // while(!a.IsEmpty())
    // {
    //     std::cout<<(long)*a.GetTop()<<" ";
    //     a.Pop();
    // }
    // std::cout<<std::endl;

    // if(argc != 3)
    // {
    //     std::cout <<"参数不对!\n";
    //     return -1;
    // }

    // 进制转换器
    // LinkStack s;
    // int num = 31;
    // int n = 16;
    // while (num != 0)
    // {
    //     s.Push((void *)(long)(num % n));
    //     num /= n;
    // }

    // while (!s.IsEmpty())
    // {
    //     long number = (long)*s.GetTop();
    //     if (number <= 9)
    //         std::cout << number;
    //     else
    //         std::cout << (char)(number - 10 + 'a');
    //     s.Pop();
    // }
    // std::cout << std::endl;






    int a[] = {5,4,2,1,3};
    Fast_No_Recur(a,0,4);
    for(int i =0;i<5;i++)
    {
        std::cout<<a[i]<<" ";
    }
    std::cout<<std::endl;





    return 0;
}